package find.the.number.that.is.only;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @Time 2019/12/11
 * @author 王光浩
 * @Method 需求：在一个非空的数组中，每个数字都会出现两次，除了一个特别的数字，找出那个特别的数字
 *         思路1：使用hashset获得特定的数字
 *         复杂度：时间复杂度——由于使用了judge方法，时间复杂为O（n），空间复杂度O（n）
 *         思路2：使用排序的方法来获得特定的数字
 *         复杂度：时间复杂度——使用Arrays的sort方法，时间复杂度为O（nlogn),空间复杂度为O（1）
 *         思路3：将所有数据相加，然后将结果对2进行求余，所得结果就是特殊的数字
 *   
 */
public class MyMethodOne {
	/**第一种方法的实现，设计一个累加器，然后便利数组如果元素不存在hashset中累加器进行累加，否则将累加器减去该数值，最后的结果就
	 * 是特殊的数字*/
    public int singleNumberOne(int[] nums) {
        int result=0;                             //累计器
        HashSet<Integer> judge=new HashSet<Integer>();
        int len=nums.length;
        for(int i=0;i<len;i++) {
        	if(judge.add(nums[i]))
        		result+=nums[i];
        	else
        		result-=nums[i];
        }
        return result;
    }
    
    /**第二种方法的实现，现将数组元素进行排序，然后便利查找不同*/
    public int singleNumberTwo(int[] nums) {
    	Arrays.sort(nums);
    	int len=nums.length;
    	for(int i=0;i<len-1;i+=2) {    //将数组元素-1个元素进行比较
    		if(nums[i]==nums[i+1])
    			continue;
    		return nums[i];
    	}
    	return nums[len-1];
    }

}
